Modularna aritmetika

V matematiki je modularna aritmetika sistem aritmetike za cela števila, kjer se števila "ponovno vrtijo okoli", ko dosežejo določeno vrednost, ki se imenuje modulo (ali modul). Moderni približek modularni aritmetiki je uveljavil Carl Friedrich Gauss v svoji knjigi Disquisitiones Arithmeticae, ki jo je izdal leta 1801.

Vsem poznana uporaba modularne aritmetike je 12-urna ura, kjer je dan razdeljen na dve 12-urni periodi. Če je sedaj ura 7:00, bo čez 8 ur enaka 3:00. Navadno seštevanje bi nam dalo rezultat 7 + 8 = 15, a to ne bo odgovor, ker se čas po uri "obrne naokoli" na vsakih 12 ur. Ker se številke na uri ponastavijo, ko pridejo do 12, ima ura aritmetični modul enak 12. Če to izrazimo s spodnjo definicijo, je 15 kongruentno 3 v modulu 12, torej je (24-urni) čas "15:00" enak času "3:00" na uri.

Definicije relacij v konguencah

Modularna aritmetika se lahko obravnava matematično z vpeljavo kongruenčne relacije na celih številih, ki se da združiti z operacijami na celih številih: seštevanje, odštevanje in množenje. Za naravno število $n$ , sta dve števili $a$ in $b$ kongruentni v modulu $n$ , če je njuna razlika $a - b$ celi večkratnik od $n$ (torej če obstaja tako celo število $k$ , da velja $a - b = kn$ ). Ta kongruenčna relacija se običajno šteje, ko sta $a$ in $b$ celi števili, označi pa se jo z:

a\equiv b{\pmod {n}}.

Oklepaji pomenijo, da $(mod n)$ velja za celo enačbo, ne samo za desno stran (v tem primeru b). Včasih se uporablja tudi $=$ namesto $\equiv$ . Če se oklepaje izpusti, pomeni to v splošnem, da označuje "mod" operacijo modulo, ki se nanaša samo na desno stran, spremeni pa se tudi v enakost, da velja $0 \leq a < n$ .

Število $n$ se imenuje modul kongruence.

Kongruenčna relacija se lahko zapiše tudi kot

a=kn+b,

kar eksplicitno prikaže Evklidsko deljenje. Kaj pa če $b$ ni ostanek števila $a$ pri deljenju z $n$ ? Bolj natančno lahko relacijo $a \equiv b mod n$ opišemo tako, da morata tako $a$ , kot tudi $b$ imeti enak ostanek pri deljenju z $n$ . Torej

a=pn+r,

b=qn+r,

kjer je $0 \leq r < n$ skupni delitelj. Če odštejemo ta dva izraza, pridemo do prejšnje relacije:

a-b=kn,

kjer definiramo $k = p - q .$

Primeri

Na primer

38\equiv 14{\pmod {12}}\,

ker je $38 - 14 = 24$ , kar je večkratnik od 12, ali, ekvivalentno, ker imata tako 38, kot tudi 14 enak ostanek 2 pri deljenju z 12.

Enako pravilo velja tudi za negativne vrednosti:

{\begin{aligned}-8&\equiv 7{\pmod {5}}\\2&\equiv -3{\pmod {5}}\\-3&\equiv -8{\pmod {5}}.\end{aligned}}

Ker se lahko pogosto pojavi več relacij, kjer so različni moduli naenkrat, smo v zgornji sistem vedno zapisali modulo. Kongruenčna relacija za dani modul velja za binarno relacijo.

Lastnosti

Kongruenčna relacija zadovolji vsem pogojem za ekvivalenčno relacijo:

Refleksivnost: $a \equiv a (mod n)$
Simetrija: $a \equiv b (mod n)$ če $b \equiv a (mod n)$ za vse $a$ , $b$ in $n$ .
Tranzitivnost: Če $a \equiv b (mod n)$ in $b \equiv c (mod n)$ , potem $a \equiv c (mod n)$

Če velja $a 1 \equiv b 1 (mod n)$ in $a 2 \equiv b 2 (mod n),$ ali če velja $a \equiv b (mod n),$ potem:

$a + k \equiv b + k (mod n)$ za katerokoli celo število $k$ (kar se sklada s premikom)
$k a \equiv k b (mod n)$ za katerokoli celo število $k$ (kar je skladno s povečanjem)
$a 1 + a 2 \equiv b 1 + b 2 (mod n)$ (skladno s seštevanjem)
$a 1 - a 2 \equiv b 1 - b 2 (mod n)$ (skladno z odštevanjem)
$a 1 a 2 \equiv b 1 b 2 (mod n)$ (skladno z množenjem)
$a k \equiv b k (mod n)$ za katerokoli nenegativno celo število $k$ (skladno s potenciranjem)
$p (a) \equiv p (b) (mod n)$ , za katerikoli polinom $p (x)$ s celimi koeficienti (kar je skladno s polinomsko evaluacijo)

Če je $a \equiv b (mod n)$ , potem v splošnem ni pravilno $k a \equiv k b (mod n)$ . A to velja, če velja sledeči pogoj:

Če velja $c \equiv d (mod φ (n)),$ kjer je $φ$ Eulerjeva funkcija, potem $a c \equiv a d (mod n)$ , če je $a$ tuja z $n$

Za pokrajšanje skupnih členov, poznamo sledeča pravila:

Če je $a + k \equiv b + k (mod n)$ za katerokoli celo število $k$ , potem je $a \equiv b (mod n)$
Če je $k a \equiv k b (mod n)$ in sta si $k$ in $n$ tuji si števili, potem je $a \equiv b (mod n)$

Modularni multiplikativni inverz je definiran s sledečimi pravili:

Obstoj: obstaja celo število, ki je označeno z $a -1$ , da velja $aa -1 \equiv 1 (mod n)$ če in samo če je $a$ tuje z $n$ . To število $a -1$ se imenuje modularni multiplikativni inverz modula $n$ .
Če je $a \equiv b (mod n)$ in obstaja $a -1$ , potem je $a -1 \equiv b -1 (mod n)$ (skladno z multiplikativnim inverzom in če ima $a = b$ edinstven modul $n$ )
Če je $a x \equiv b (mod n)$ in $a$ je tuje $n$ , potem je rešitev te linearne kongruence podana z $x \equiv a -1 b (mod n)$

Multiplikativni inverz $x \equiv a -1 (mod n)$ se lahko učinkovito izračuna z uporabo Bézoutove identitete $ax+ny=1$ za $x,y$ z uporabo razširjenega Evklidovega algoritma. V posebnem, če je $p$ praštevilo, potem sta si $a$ in $p$ tuji za vsak $a$ , da velja $0 < a < p$ ; torej multiplikativni inverz obstaja za vse $a$ , ki niso kongruentni ničelnemu modulu $p$ .

Nekaj nekaterih bolj naprednih lastnosti kongruenčnih relacij je zbranih tukaj:

Fermatov mali izrek: Če je $p$ praštevilo in ne deli $a$ , potem $a p - 1 \equiv 1 (mod p)$ .
Eulerjev izrek: Če sta si $a$ in $n$ tuji si števili, potem velja $a φ (n) \equiv 1 (mod n)$ , kjer je $φ$ Eulerjeva funkcija fi
Preprosta posledica Fermatovega malega izreka je: če je $p$ praštevilo, potem je $a -1 \equiv a p - 2 (mod p)$ multiplikativni inverz od $0 < a < p$ . Še bolj splošno iz Eulerjevega izreka: če sta si $a$ in $n$ tuji, potem je $a -1 \equiv a φ (n) - 1 (mod n)$ .
Druga preprosta posledica je, da če velja $a \equiv b (mod φ (n)),$ kjer je $φ$ Eulerjeva fi funkcija, potem velja $k a \equiv k b (mod n)$ , kjer je $k$ tuje z $n$ .
Wilsonov izrek: $p$ je praštevilo, če in samo če velja $(p - 1)! \equiv -1 (mod p)$ .
Kitajski izrek o ostankih: Za katerakoli $a$ in $b$ ter tuji števili $m$ in $n$ , obstaja unikatno celo število $x (mod mn)$ , da velja $x \equiv a (mod m)$ in $x \equiv b (mod n)$ . Velja tudi $x \equiv b m n -1 m + a n m -1 n (mod mn)$ , kjer je $m n -1$ inverz od $m$ modulo $n$ in $n m -1$ je inverz od $n$ modulo $m$ .
Lagrangeov izrek: Kongruenca $f (x) \equiv 0 (mod p)$ , kjer je $p$ praštevilo in $f (x) = a 0 x n + ... + a n$ je polinom s celimi koeficienti, da ima $a 0 \neq 0 (mod p)$ največ $n$ korenov.
Primitivni koren modula n: Število $g$ je primitivni koren modula $n$ , če obstaja za vsako celo število $a$ , ki je tuje $n$ , neko celo število $k$ , da velja $g k \equiv a (mod n)$ . Primitivni koren modula $n$ obstaja če in samo če je $n$ enak $2, 4, p k$ ali $2 p k$ , kjer je $p$ liho praštevilo in je $k$ naravno število. Če obstaja primitivni koren modula $n$ , potem obstaja natanko $φ (φ (n))$ takšnih primitivnih korenov, kjer je $φ$ Eulerjeva fi funkcija.
Kvadratični ostanek: Celo število $a$ je kvadratični ostanek modula $n$ , če obstaja tako celo število $x$ , da velja $x 2 \equiv a (mod n)$ . Eulerjev kriterij nam pravi, da če je $p$ liho praštevilo in a ni večkratnik od p, potem je $a$ kvadratični ostanek modula $p$ če in samo če

a^{\frac {p-1}{2}}\equiv 1{\pmod {p}}.

Kongruenčni razredi

Kot katerakoli kongruenčna relacija, je kongruenčni modulo $n$ ekvivalenčna relacija ter ekvivalenčni razred celega števila $a$ , ki se označi z $a n$ , je množica ${\dots , a - 2 n, a - n, a, a + n, a + 2 n, \dots}$ . Ta množica, ki jo sestavljajo cela števila, ki so kongruentna $a$ po modulu $n$ , se imenuje kongruenčni razred ali razred ostankov ali preprosto ostanek celega števila $a$ , po modulu $n$ . Če je modulo $n$ razpoznaven iz besedila, se lahko ta ostanek označi z $[a]$ .

Primeri implementacij

Spodaj so tri dokaj hitre funkcije v jeziku C, dve za izvajanje modularnih množenj in ena za izvajanje modularnega potenciranja na neoznačenih celih (naravnih) številih, ki niso večja od 63 bitov.

Algoritemski način za izračunanje $a\cdot b{\pmod {m}}$ :

uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)
{
   uint64_t d = 0, mp2 = m >> 1;
   int i;
   if (a >= m) a %= m;
   if (b >= m) b %= m;
   for (i = 0; i < 64; ++i)
   {
       d = (d > mp2) ? (d << 1) - m : d << 1;
       if (a & 0x8000000000000000ULL)
           d += b;
       if (d >= m) d -= m;
       a <<= 1;
   }
   return d;
}

Na računalnikih, kjer je mogoča tudi razširjena natančnost z najmanj 64 biti mantise (kot recimo tip long double na večini x86 C prevajalnikih), se lahko uporabi sledeča implementacija, saj po trdih komponentah množenje plavajoče vejice vodi v obdržane najbolj zanesljive bite, medtem ko množenje celih števil vodi v obdržane najmanj zanesljive bite:

uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)
{
   long double x;
   uint64_t c;
   int64_t r;
   if (a >= m) a %= m;
   if (b >= m) b %= m;
   x = a;
   c = x * b / m;
   r = (int64_t)(a * b - c * m) % (int64_t)m;
   return r < 0 ? r + m : r;
}

Spodnja je C funkcija za izvajanje modularnega potenciranja, ki uporablja funkcijo $mul_mod$ , ki je bila implementirana zgoraj. Algoritemski način za izračunanje $a^{b}{\pmod {m}}$ :

uint64_t pow_mod(uint64_t a, uint64_t b, uint64_t m)
{
    uint64_t r = m==1?0:1;
    while (b > 0) {
        if (b & 1)
            r = mul_mod(r, a, m);
        b = b >> 1;
        a = mul_mod(a, a, m);
    }
    return r;
}

A da bi vse zgornje poti delovale, ne sme $m$ prekoračiti 63 bitov.

Glej tudi

Booleanov obroč
Krožno blažilnik
Deljenje (matematika)
Končno polje
Legendrov simbol
Modularno potenciranje
Pisanova perioda (Fibonaccijevo zaporedje modula n)
Primitivni koren modula n
Kvadratna recipročnost
Kvadratni ostanek
Racionalna rekonstrukcija (matematika)
Zmanjšani sistem ostankov
Aritmetika serijskih števil (poseben primer modularne aritmetike)
Booleanova algebra dveh elementov
Področja, ki se nanašajo na teorijo grup za modularno aritmetiko:
- Ciklična grupa
- Multiplikativna grupa celih števil modula n
Ostali pomembni izreki, ki se nanašajo na modularno aritmetiko:
- Carmichaelov izrek
- Kitajski izrek o ostankih
- Eulerjev izrek
- Fermatov mali izrek (posebni primer Eulerjevega izreka)
- Lagrangeov izrek
- Thueova lema

Sklici

Viri

John L. Berggren. "modular arithmetic". Encyclopædia Britannica.
Apostol, Tom M. (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, MR 0434929, Zbl 0335.10001. See in particular chapters 5 and 6 for a review of basic modular arithmetic.
Maarten Bullynck "Modular Arithmetic before C.F. Gauss. Systematisations and discussions on remainder problems in 18th-century Germany"
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7 ISBN 0-262-03293-7. Section 31.3: Modular arithmetic, pp. 862–868.
Anthony Gioia, Number Theory, an Introduction Reprint (2001) Dover. ISBN 0-486-41449-3 ISBN 0-486-41449-3.
Long, Calvin T. (1972). Elementary Introduction to Number Theory (2. izd.). Lexington: D. C. Heath and Company. LCCN 77171950.
Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). Elements of Number Theory. Englewood Cliffs: Prentice Hall. LCCN 71081766.
Sengadir, T. (2009). Discrete Mathematics and Combinatorics. Chennai, India: Pearson Education India. ISBN 978-81-317-1405-8. OCLC 778356123.

Zunanje povezave

Hazewinkel, Michiel, ed. (2001) [1994], "Congruence", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
V tem članku o modularni umetnosti se lahko vsak nauči nekaj o uporabi modularne aritmetike v umetnosti.
Weisstein, Eric Wolfgang. »Modular Arithmetic«. MathWorld.
Članek o modularni aritmetiki na wikiju GIMPS
Modularna aritmetika in vzorci v seštevanju in tabele množenja